import java.util.Objects;

class Person {

    public String id;

    Person(String id) {
        this.id = id;
    }

    //自定义类型需要重写equals和hashCode方法
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof Person)) return false;
        Person person = (Person) o;
        return Objects.equals(id, person.id);
    }

    @Override
    public int hashCode() {
        return Objects.hashCode(id);
    }
}

public class HashBuck<K, V> {

    static class Node<K, V> {
        public K key;

        public V val;

        public Node<K, V> next;

        public Node(K key, V val) {
            this.key = key;
            this.val = val;
        }
    }

    public Node<K, V>[] array;

    public int usedSize;

    public HashBuck() {
        //需要强转
        array = (Node<K, V>[])new Node[10];
    }

    public void put(K key, V val) {
        //定义一个hash
        int hash = key.hashCode();
        //找到元素将要存放的位置
        int index = hash % array.length;
        Node<K, V> cur = array[index];


        //先遍历一遍  是否存在key
        while (cur != null) {
            //自定义类型不能用 = 比较  要用equals
            if (cur.key.equals(key)) {
                //能找到key  更新key对应的val
                cur.val = val;
                return;
            }
            cur = cur.next;
        }
        //哈希桶中没有这个key
        //将新元素添加到哈希桶中
        Node<K, V> node = new Node<>(key, val);
        node.next = cur;
        array[index] = node;
        usedSize++;
        if(loadFactor() >= 0.75){
            resize();
        }
    }

    public V get(K key) {
        int hash = key.hashCode();
        int index = hash % array.length;
        Node<K, V> cur = array[index];
        while (cur != null) {
            if (cur.key.equals(key)) {
                return cur.val;
            }
            cur = cur.next;
        }
        return null;
    }

    private double loadFactor() {
        return usedSize * 1.0 / array.length;
    }

    private void resize(){
        Node<K, V>[] tmpArray = (Node<K, V>[])new Node[array.length*2];
        //遍历原来的数组  将数组中的所有元素重新哈希到新的数组当中
        for(int i = 0; i < array.length; i++){
            Node<K, V> cur = array[i];
            while(cur != null){
                //计算新的位置
                int hash = cur.key.hashCode();
                int newIndex = hash % array.length;
                //记录当前节点的下一个节点
                Node curNext = cur.next;
                curNext.next = tmpArray[newIndex];
                tmpArray[newIndex] = cur;
                cur = curNext;
            }
        }
        array = tmpArray;
    }
}
